package com.LeeCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 基于时间的键值存储
 */

public class Code981 {
    public static void main(String[] args) {
        TimeMap timeMap = new Code981().new TimeMap();
        timeMap.set("love", "high", 10);
        timeMap.set("love", "low", 20);


    }

    class TimeMap {

        class Node {
            int timestamp;
            String value;

            public Node(int timestamp, String value) {
                this.timestamp = timestamp;
                this.value = value;
            }
        }

        HashMap<String, List<Node>> map;

        public TimeMap() {
            map = new HashMap<>();
        }

        public void set(String key, String value, int timestamp) {
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            List<Node> nodes = map.get(key);
            nodes.add(new Node(timestamp, value));
        }

        public String get(String key, int timestamp) {
            List<Node> nodes = map.get(key);
            if (nodes == null) return "";
            int pos = lowerBound(nodes, timestamp + 1) - 1;
            if (pos < 0) return "";
            return nodes.get(pos).value;
        }

        private int lowerBound(List<Node> nodes, int target) {
            int left = -1, right = nodes.size(), mid;
            while (left + 1 < right) {
                mid = left + (right - left) / 2;
                if (nodes.get(mid).timestamp >= target) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;
        }
    }
}
